package org.basis.algorithm.list.common;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.function.BiFunction;

/**
 * 链表节点工具类
 *
 * @author Mr_wenpan@163.com 2021/12/08 17:46
 */
public class ListNodeUtil {

    /**
     * 生成int类型的单向链表
     */
    public static SingleNode<Integer> generateIntegerSingleList(int listLength, int maxNumber, boolean needOrder) {
        return generateSingleList(listLength, maxNumber, needOrder, Comparator.comparingInt(o -> o.data),
                (length, number) -> (int) ((maxNumber + 1) * Math.random()) - (int) (maxNumber * Math.random()));
    }

    /**
     * 生成一个单向链表(通用方法)
     *
     * @param listLength 链表长度
     * @param maxNumber  链表中元素值最大值
     * @param needOrder  是否需要链表节点有序
     * @param comparator 节点大小比较器
     * @param biFunction 函数式接口
     * @return org.basis.algorithm.list.common.SingleNode<T> 返回单向链表头节点
     */
    public static <T extends Comparable<T>> SingleNode<T> generateSingleList(int listLength,
                                                                             int maxNumber,
                                                                             boolean needOrder,
                                                                             Comparator<SingleNode<T>> comparator,
                                                                             BiFunction<Integer, Integer, T> biFunction) {
        if (listLength < 1) {
            return null;
        }
        // 优先级队列，按照节点大小组织，如何排序由调用方传入的比较器决定
        PriorityQueue<SingleNode<T>> priorityQueue = new PriorityQueue<>(comparator);
        // linkedlist 按加入顺序有序
        LinkedList<SingleNode<T>> linkedList = new LinkedList<>();
        for (int i = 0; i < listLength; i++) {
            // 随机生成节点值的方法由调用方自己实现
            SingleNode<T> singleNode = new SingleNode<>(biFunction.apply(listLength, maxNumber));
            if (needOrder) {
                priorityQueue.add(singleNode);
            } else {
                linkedList.add(singleNode);
            }
        }

        SingleNode<T> head;
        if (needOrder) {
            head = priorityQueue.poll();
        } else {
            head = linkedList.pollFirst();
        }

        // 记录头节点
        SingleNode<T> resHead = head;
        // 组织链表关系
        while (head != null) {
            SingleNode<T> poll;
            if (needOrder) {
                poll = priorityQueue.poll();
            } else {
                poll = linkedList.poll();
            }
            if (poll == null) {
                break;
            }
            head.next = poll;
            head = head.next;
        }

        return resHead;
    }

    /**
     * 生成整形的双向链表的公用方法
     */
    public static PairNode<Integer> generateIntegerPairList(Integer listLength, Integer maxNumber, boolean needOrder) {
        return generatePairList(listLength, maxNumber, needOrder, Comparator.comparingInt(o -> o.data),
                (length, number) -> (int) ((maxNumber + 1) * Math.random()) - (int) (maxNumber * Math.random()));
    }

    /**
     * 生成一个双向链表（通用方法，适合于任何类型的数据类型，但必须要实现Comparable接口）
     *
     * @param listLength 链表长度
     * @param maxNumber  链表中元素值最大值
     * @param needOrder  是否需要链表节点有序
     * @param comparable 节点大小比较器
     * @param biFunction 函数式接口
     * @return org.basis.algorithm.list.common.PairNode<T> 返回双向链表头节点
     */
    public static <T extends Comparable<T>> PairNode<T> generatePairList(Integer listLength,
                                                                         Integer maxNumber,
                                                                         boolean needOrder,
                                                                         Comparator<PairNode<T>> comparable,
                                                                         BiFunction<Integer, Integer, T> biFunction) {
        if (listLength < 1) {
            return null;
        }
        // 优先级队列，按照节点大小组织，按照节点数据大小排升序
        PriorityQueue<PairNode<T>> priorityQueue = new PriorityQueue<>(comparable);
        // linkedlist 按加入顺序有序
        LinkedList<PairNode<T>> linkedList = new LinkedList<>();
        for (int i = 0; i < listLength; i++) {
            // 随机生成一个值，该方法由调用方自己决定如何生成
            PairNode<T> pairNode = new PairNode<>(biFunction.apply(listLength, maxNumber));
            if (needOrder) {
                priorityQueue.add(pairNode);
            } else {
                linkedList.add(pairNode);
            }
        }

        PairNode<T> head;
        if (needOrder) {
            head = priorityQueue.poll();
        } else {
            head = linkedList.pollFirst();
        }

        // 记录头节点
        PairNode<T> resHead = head;
        // 组织链表关系
        while (head != null) {
            PairNode<T> poll;
            if (needOrder) {
                poll = priorityQueue.poll();
            } else {
                poll = linkedList.poll();
            }
            if (poll == null) {
                break;
            }
            head.next = poll;
            poll.last = head;
            head = head.next;
        }

        return resHead;
    }

    /**
     * 打印单链表
     *
     * @param head 头节点
     */
    public static <T extends Comparable<T>> void printSingleList(SingleNode<T> head) {
        while (head != null) {
            System.out.print(head.data + "   ");
            head = head.next;
        }
        System.out.println();
    }

    /**
     * 打印双向链表
     *
     * @param head 头节点
     */
    public static <T extends Comparable<T>> void printPairList(PairNode<T> head) {
        while (head != null) {
            System.out.print(head.data + "   ");
            head = head.next;
        }
        System.out.println();
    }

    /**
     * 双向链表是否相等
     */
    public static <T extends Comparable<T>> boolean isPairListEquals(PairNode<T> head1, PairNode<T> head2) {
        if (head1 == null && head2 == null) {
            return true;
        }
        if (head1 == null || head2 == null) {
            return false;
        }
        while (head1 != null && head2 != null) {
            if (head1.data != head2.data) {
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return head1 == null && head2 == null;
    }

    /**
     * 单向链表是否相等
     */
    public static <T extends Comparable<T>> boolean isSingleListEquals(SingleNode<T> head1, SingleNode<T> head2) {
        if (head1 == null && head2 == null) {
            return true;
        }
        if (head1 == null || head2 == null) {
            return false;
        }
        while (head1 != null && head2 != null) {
            if (head1.data != head2.data) {
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return head1 == null && head2 == null;
    }

}
